/*
 * @lc app=leetcode.cn id=96 lang=typescript
 *
 * [96] 不同的二叉搜索树
 */

// @lc code=start

//  思路：动态规划
//  取决于在哪一点断开，F(n)表示由1-n可组成的二叉搜索树个数，可断开的点i从1-n
//  状态转移方程：F(n) = Σ(i=1-n) F(i-1) * F(n-i)

//  复杂度：O(n2) O(n)
//  还有数学公式法，复杂度可以降为 O(n) O(1)
//  https://leetcode-cn.com/problems/unique-binary-search-trees/solution/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/

function numTrees(n: number): number {
    const res = new Array(n + 1).fill(0)
    res[0] = res[1] = 1
    for (let i = 2; i <= n; i++) {
        for (let j = 1; j <= i; j++) {
            res[i] += res[j - 1] * res[i - j]
        }
    }
    return res[n]
};
// @lc code=end

console.log(numTrees(3))
